#include "../tools.h"

struct Tweet{
    int id;
    int timestamp;
    Tweet *next;
    bool operator<(const Tweet& b) const {
        return timestamp < b.timestamp;
    }
    Tweet(int _id, int _timestamp): id(_id), timestamp(_timestamp), next(nullptr){}
};

class Twitter {
private:
    // 用户关注表
    unordered_map<int, set<int>>    userid_followerids;
    // 用户消息链表 写，查有序
    unordered_map<int, Tweet*>      userid_tweetids;
    // 全局时间戳
    int now_timestamp;
public:
    Twitter() {
        now_timestamp = 0;
    }
    
    void postTweet(int userId, int tweetId) {
        ++now_timestamp;
        if(!userid_tweetids.count(userId)) 
            userid_tweetids[userId] = new Tweet(tweetId, now_timestamp);
        else{ // 头插
            auto p = new Tweet(tweetId, now_timestamp);
            p->next = userid_tweetids[userId];
            userid_tweetids[userId] = p;
        }
    }
    
    vector<int> getNewsFeed(int userId) {
        if(!userid_followerids.count(userId) && !userid_tweetids.count(userId)) return {};

        set<int> followers = userid_followerids[userId];
        vector<int> newsFeed;
        priority_queue<Tweet*> q;
        // 自己的
        if(userid_tweetids.count(userId)) q.push(userid_tweetids[userId]);
        // 关注的
        if(userid_followerids.count(userId)){
            auto followers = userid_followerids[userId];
            for(auto follower: followers) {
                if(userid_tweetids.count(follower)) q.push(userid_tweetids[follower]);
            }
        }

        // top 10
        for(int i = 0; !q.empty() && i < 10; ++i){
            Tweet* t = q.top();
            newsFeed.push_back(t->id);
            q.pop();
            if(t->next) q.push(t->next);
        }

        return newsFeed;
    }
    
    void follow(int followerId, int followeeId) {
        if(followerId == followeeId) return;

        if(!userid_followerids.count(followerId)) userid_followerids[followerId] = set<int>{followeeId};
        else
            userid_followerids[followerId].insert(followeeId);
    }
    
    void unfollow(int followerId, int followeeId) {
        if(!userid_followerids.count(followerId) || !userid_followerids[followerId].count(followeeId)) return;

        userid_followerids[followerId].erase(followeeId);
    }
};

int main(int argc, char const *argv[])
{
    vector<int> param_2;

    Twitter* obj = new Twitter();
    obj->postTweet(1,5);
    param_2 = obj->getNewsFeed(1);
    show(param_2);

    obj->follow(1,2);
    obj->postTweet(2,6);
    param_2 = obj->getNewsFeed(2);
    show(param_2);
    param_2 = obj->getNewsFeed(1);
    show(param_2);
    obj->unfollow(1,2);
    param_2 = obj->getNewsFeed(1);
    show(param_2);

    return 0;
}
